import time


class Concept:
    def __init__(self, extent, intent):
        self.extent = sorted(extent)  # 外延 (对象集合)，排序以确保一致性
        self.intent = sorted(intent)  # 内涵 (属性集合)，排序以确保一致性
        self.visited = False  # 标记是否已访问
        self.NewConcept = None  # 存储候选新概念
        self.doExtent = None  # 存储传入的外延值
        self.MaximalConcept = None  # 存储最大概念
        self.children = []  # 存储子概念

    def __repr__(self):
        return "Concept(Extent={'.'.join(self.extent)}, Intent={'.'.join(self.intent)})"  # 保证内涵顺序

    def __eq__(self, other):
        if not isinstance(other, Concept):
            return False
        return set(self.extent) == set(other.extent) and set(self.intent) == set(other.intent)

    def __hash__(self):
        return hash((tuple(self.extent), tuple(self.intent)))


class ConceptLattice:
    def __init__(self):
        self.concepts = []  # 存储所有概念
        self.extent_map = {}  # 存储外延值到概念的映射 (用于加速查找)
        self.intent_map = {}  # 存储内涵值到概念的映射（用于去重）

    def add_concept(self, concept):
        # 如果已经存在相同外延和内涵的概念，则不添加
        if concept in self.concepts:
            return
        self.concepts.append(concept)
        self.extent_map[tuple(concept.extent)] = concept
        self.intent_map[tuple(concept.intent)] = concept

    def find_concept_by_extent(self, extent):
        return self.extent_map.get(tuple(extent), None)

    def find_concept_by_intent(self, intent):
        return self.intent_map.get(tuple(intent), None)


def calculate_intent(extent, I0):
    """
    计算给定对象集合 extent 的内涵 f(A)
    :param extent: 对象集合 A
    :param I0: 二元关系字典 {对象: [属性]}
    :return: 属性集合
    """
    if not extent:
        return set()  # 空的外延返回空内涵

    intent = set(I0[next(iter(extent))])  # 取第一个对象的属性集合
    for obj in extent:
        intent &= set(I0[obj])  # 取交集，得到共同拥有的属性
    return intent


def FastAddExtent(extent, generatorConcept, lattice, new_attribute, I0):
    """
    增量生成新概念，并将其添加到概念格中
    :param extent: 外延集合
    :param generatorConcept: 生成器概念
    :param lattice: 概念格
    :param new_attribute: 新增的属性
    :param I0: 二元关系字典
    """
    generatorConcept.doExtent = extent
    generatorConcept.MaximalConcept = generatorConcept
    generatorConcept = GetClosureConcept(extent, generatorConcept, lattice)
    candidate_children = generatorConcept.children
    newConcept = None

    # 处理候选子概念，生成新概念
    for candidate in candidate_children:
        if set(candidate.extent).issubset(extent):
            newConcept = candidate
        else:
            newConcept = Concept(extent, calculate_intent(extent, I0))
            lattice.add_concept(newConcept)
            candidate.NewConcept = newConcept
            candidate.visited = True

    if newConcept is None:
        newConcept = Concept(extent, calculate_intent(extent, I0))  # 创建新概念
        lattice.add_concept(newConcept)

    if not newConcept.visited:
        newConcept.NewConcept = Concept(extent, calculate_intent(extent, I0))
        lattice.add_concept(newConcept)

    for child in candidate_children:
        if not child.visited:
            child.NewConcept = newConcept
            child.visited = True

    return newConcept


def GetClosureConcept(extent, generatorConcept, lattice):
    """
    获取外延的闭包概念
    :param extent: 外延集合
    :param generatorConcept: 生成器概念
    :param lattice: 概念格
    :return: 闭包概念
    """
    concept = lattice.find_concept_by_extent(extent)
    if concept:
        return concept
    for child in generatorConcept.children:
        if set(child.extent).issubset(extent):
            return child
    return generatorConcept


def CreateLatticeIncrementally(G, M, I0):
    """
    增量式创建概念格
    :param G: 对象集合
    :param M: 属性集合
    :param I0: 二元关系字典
    :return: 概念格
    """
    lattice = ConceptLattice()
    topConcept = Concept([], M)  # topConcept的内涵是所有属性
    lattice.add_concept(topConcept)

    for new_attribute in M:
        extent = [g for g in G if new_attribute in I0[g]]  # 根据属性生成外延
        FastAddExtent(extent, topConcept, lattice, new_attribute, I0)

    # 强制添加包含所有对象的全外延概念
    full_extent_concept = Concept(G, set())  # 全外延概念，内涵为空集
    lattice.add_concept(full_extent_concept)

    return lattice


def read_data(file_path):
    """
    读取数据文件并解析为对象和属性的集合
    :param file_path: 数据文件路径
    :return: G, M, I0
    """
    with open(file_path, 'r') as file:
        line = file.readline().strip()
        num_objects, num_attributes = map(int, line.split(','))

        G = [str(i + 1) for i in range(num_objects)]  # 对象集合 ['1', '2', ..., '5']
        M = [chr(ord('a') + i) for i in range(num_attributes)]  # 属性集合 ['a', 'b', ..., 'g']

        I0 = {}
        for i in range(num_objects):
            line = file.readline().strip()
            attributes = list(map(int, line.split(',')))
            I0[G[i]] = [M[j] for j in range(num_attributes) if attributes[j] == 1]

        return G, M, I0


if __name__ == "__main__":
    start = time.time()

    # 读取数据
    file_path = './experiment04/abalone.txt'  # 文件路径
    G, M, I0 = read_data(file_path)

    # 创建增量概念格
    lattice = CreateLatticeIncrementally(G, M, I0)

    # 输出生成的概念格
    print("Concept Lattice:")
    for concept in lattice.concepts:
        print(concept)
    print(len(lattice.concepts))
    print(time.time() - start)
